Міністерство освіти і науки України Національний університет ″Львівська політехніка″
Звіт про виконання лабораторної роботи №2 з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ” на тему: “ ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ ” Мета роботи: вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел. Завдання: Домашня підготовка до роботи 1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами. 2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача. 3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати. № з/п Операції з довгими числами  2 Швидке множення   Робота в лабораторії 1) Ввести в комп'ютер програми згідно з отриманим завданням. 2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками. 3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи. 4) Здати звіт з лабораторної роботи. Блок -схема головної програми Блок-схема алгоритму швидкого множення Список ідентифікаторів констант, змінних і функцій, використаних у головній програмі і підпрограмах , та їх пояснення MaxDigit – константа що вказує на максимальну довжину масиву; Osn – константа що вказує на основу; Input() ввід довгого числа з клавіатури; Output() вивід довгого числа на екран; Quick()швидке множення двох довгих чисел ; ch – елемент типу CHAR; masCh – массив елементів типу CHAR; a[] – массив, що представляє довге число; b[]– массив, що представляє довге число; c[]– массив, що представляє довге число; i, j, k – цілі змінні, що використовуються в циклі. Остаточна версія програми #include <iostream> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <ctype.h> #define MaxDig 100 #define Osn 10000 using namespace std; long int *Input( char masivCh[]) { long int *a,a22; char ch; a = (long int*)malloc(MaxDig*sizeof(int)); int i=0, j=0; for(i=0; i<MaxDig; i++) { a[i]=0; } a[0]=1; for(j=0; masivCh[j] != NULL; j++) {ch=masivCh[j]; if (isdigit(ch)) { for (i=a[0]; i>=1; i--) { a[i+1]=a[i+1]+(a[i]*10)/Osn; a[i]=a[i]*10%Osn; } a22=atoi(&ch); a[1]=a[i+1]+a22; if (a[a[0]+1]>0) a[0]++; } } return a; } void Output(long int *b) { long int result; int k=0, r=1,p,b_Osn=b[0],i=0; for(i=b[0]; i>=1; i--) { k=b[i]; if (k==0) r=0; for (p=1; k>0; p=p*10) { k=k/10; } while (Osn-p!=0) { if (b[0]==i) break; printf("%c",'0'); p=p*10; } if (r==1) { result=b[i]; printf("%d",result); } r=1; k=0; } } bool parne(long int* b) { bool c; if(b[b[0]]%2==0) c=true; else c=false; return c; } long int* dil(long int*b) { long int Ost,B; int i; Ost=0; for(i=1; i<MaxDig;i++) {B=Ost*10+b[i]; b[i]=B/2; Ost=B%2; }return b; } bool more(long int* a,long int* b) {int i; if(a[0]<b[0]) return false; else if (a[0]>b[0])return true; else {i=a[0]; while(i>0 && a[i]==b[i]) i--; if (i==0)return false; else if (a[i]>b[i])return true; else return false; } } int chekEquality(long int* a, long int* b) { int e; if (a[0]==b[0]) {e=1; } else {e=0; } for (long i=a[0]; i>=1; i--) {if (a[i]==b[i]) {continue; } else if (a[i]==b[i]) {e=1; } else {e=0; } } r...